struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    void reorderList(ListNode *head)
    {
        if (!head->next)
            return;
        // 1. 先找到中间结点
        ListNode *low = head, *fast = head;
        ListNode *pre = nullptr;
        while (fast)
        {
            fast = fast->next;
            if (fast)
                fast = fast->next;
            pre = low;
            low = low->next;
        }
        // cout << pre->val << endl;
        pre->next = nullptr;
        // 出循环后，low指针指向后半段的第一个结点
        //  2. 反转后半部分
        ListNode *phead = new ListNode(0, nullptr);
        while (low)
        {
            // cout << low->val << endl;
            ListNode *next = low->next;
            low->next = phead->next;
            phead->next = low;
            low = next;
        }
        low = phead->next;
        delete phead;
        // 3. 然后从头插入
        ListNode *cur = head;
        // print(low);
        // print(head);
        while (low)
        {
            ListNode *nextLow = low->next;
            low->next = cur->next;
            cur->next = low;
            cur = cur->next->next;
            low = nextLow;
            // print(head);
        }
    }
};